package leetcode.code;

/**
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 *
 * push(x) —— 将元素 x 推入栈中。
 * pop() —— 删除栈顶的元素。
 * top() —— 获取栈顶元素。
 * getMin() —— 检索栈中的最小元素。
 *  
 *
 * 示例:
 *
 * 输入：
 * ["MinStack","push","push","push","getMin","pop","top","getMin"]
 * [[],[-2],[0],[-3],[],[],[],[]]
 *
 * 输出：
 * [null,null,null,null,-3,null,0,-2]
 *
 * 解释：
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.getMin();   --> 返回 -3.
 * minStack.pop();
 * minStack.top();      --> 返回 0.
 * minStack.getMin();   --> 返回 -2.
 *  
 *
 * 提示：
 *
 * pop、top 和 getMin 操作总是在 非空栈 上调用。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/min-stack
 */
public class 最小栈 {

    static class MinStack {

        int[] array;
        int size = 0;
        int[] minArray;

        /** initialize your data structure here. */
        public MinStack() {
            array = new int[5];
            size = 0;
            minArray = new int[5];
        }

        public void push(int x) {
            size++;
            if (size > array.length){
                int[] tmp = new int[size*2];
                int[] tmp1 = new int[size*2];
                System.arraycopy(array, 0, tmp, 0, array.length);
                System.arraycopy(minArray, 0, tmp1, 0, minArray.length);
                array = tmp;
                minArray = tmp1;
            }
            array[size-1] = x;
            if (size > 1){
                if (x < minArray[size-2]){
                    minArray[size-1] = x;
                }else {
                    minArray[size-1] = minArray[size-2];
                }
            }else {
                minArray[size-1] = x;
            }

        }

        public void pop() {
            size--;
        }

        public int top() {
            return array[size-1];
        }

        public int getMin() {
            return minArray[size-1];
        }
    }

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

    public static void main(String[] args){
        MinStack m = new MinStack();
        m.push(-2);
        m.push(0);
        m.push(-3);
        System.out.println(m.getMin());
        m.pop();
        System.out.println(m.top());
        System.out.println(m.getMin());
    }
}
